home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_1 / fft_kc < prev    next >
Internet Message Format  |  1995-03-31  |  11KB
  1. From: Ken Cooke <kcooke@milton.u.washington.edu>
  2. Subject:  v06i005:  fft_kc - Machine Code FFT, Part01/01
  3. Newsgroups: comp.sources.hp48
  4. Keywords: FFT
  5. Organization: University of Washington
  6. Followup-To: comp.sys.hp48
  7. Approved: spell@seq.uncwil.edu
  8.  
  9. Checksum: 1244677838 (verify with brik -cv)
  10. Submitted-by: Ken Cooke <kcooke@milton.u.washington.edu>
  11. Posting-number: Volume 6, Issue 5
  12. Archive-name: fft_kc/part01
  13.  
  14.  
  15. BEGIN_DOC fft.doc
  16. Here is some FFT code that I wrote several months ago but never got around
  17. to posting.  I tried to make it fast enough to be useful.  The code is based
  18. on the standard DIT radix-2 FFT, so the input length must be a power of 2.
  19. All intermediate math is done in 15-digit precision, which gives very accurate
  20. results. (a 1024-point FFT matches MATLAB to 12 digits)
  21.  
  22. I used the following definition of the FFT:
  23.            N-1
  24.     X[k] = Sum( x[n] * exp(-j*2pi*k*n/N) )
  25.            n=0
  26.            N-1
  27.     x[n] = 1/N Sum( X[k] * exp(j*2pi*k*n/N) )
  28.            k=0
  29.  
  30. Quick description of the programs in this UUENCODED directory:
  31.  
  32. FFT: machine code FFT.  Input is a vector (either real or complex).
  33. Size must be a power of two.  Output is a complex vector.  Includes
  34. error checking.  I believe this is as fast as the HP48 can be at a complex
  35. FFT.  Random 128-pt complex FFT: 7.5 seconds.  About 8 times faster than
  36. system RPL, and 1.5 times faster than the FFT in the HP71 mathpack after
  37. compensating for clock speed differences.  (I did not look at the mathpack
  38. code)
  39.  
  40. IFFT: inverse FFT.  Could have been combined with the FFT program, but I
  41. hate using an additional argument to tell it which one to do.
  42.  
  43. ABSV: machine code absolute value.  Input can be a vector or matrix.
  44. Output is a vector or matrix containing the absolute values of the complex
  45. elements.  About 5 times faster than RPL.
  46.  
  47. ANGLE: same as ABSV, but returns the angle (i.e. phase) according to the
  48. current angle mode.  This is only 2 or 3 times as fast as RPL, because
  49. the mcode arctan is such a bottleneck.
  50.  
  51. SPEC(trum): User code quickie that does FFT, ABSV, and then plots using the
  52. built-in barplot function.  Note that plot is from 0..2pi as returned by FFT.
  53.  
  54. DISCLAIMER
  55. While I believe these programs to be accurate and bug-free, I
  56. will assume no responsibility for any Memory Lost, hardware damage, or
  57. poor test scores that result from use of this code.
  58.  
  59. Please let me know if you find a bug or have suggestions.  I will
  60. provide the SASM source to anyone who is interested.
  61.  
  62. Ken Cooke
  63. N7VFE
  64. kcooke@u.washington.edu
  65.  
  66.  
  67. ----------------------------------------------------------------------------
  68. Machine Code FFT
  69. Copyright 1992 Ken Cooke
  70. ----------------------------------------------------------------------------
  71. END_DOC
  72.  
  73.  
  74. BEGIN_ASC fft.asc
  75. %%HP: T(1)A(R)F(.); @ tasc v2.52 file
  76. "69A20FF764A0000000403505543440D9D20E163284E203064644584E20401424
  77. 356578BF18B9C19C2A276BA1FD0D1B0DF133102AB2E193632B2130460005014E
  78. 474C45450D9D20D29512BF8171040D9D208813065226C2A16881308A7538DA16
  79. 9B136DEE324B2A224430CCD205C000823174E78FB97601431C414781AF0B1341
  80. 6E16913117E143174147174CC8A861143174164048F19930D9CE81AF0C8F88AC
  81. 0153717F13606157717F058F0ACB28F6FEA28F7D6B28F64E9207134150716F81
  82. AF1C04CE81AF0C5BA81AF138F27630B2130B2130D2100401424356540D9D20D2
  83. 9512BF8171040D9D208813065226C2A16881308A7538DA169B136DEE324B2A22
  84. 4430CCD200E000823174E78FB97601431C414781AF0813416E16913117E14317
  85. 4147174CC8A861143174164048F19930D9CE81AF0C8F88AC00572508FF6EB277
  86. 40136068F6DEB28FAC7B28F3F9B28F64E9207134150716F81AF1C04CE81AF0C5
  87. AA8DF6630153717F8FA4CB2AF9AF7AF68FE19B201B2130B21306410040946464
  88. 4540D9D20D29512BF8171040D9D20881308A7532FA306FD7388130CCD2033000
  89. 14713717414313504D6FCFA0EFEE44908D60B308DA1B306FD735C2268DA16442
  90. 30D9D20391402C2302CE3011920CA000CBD30D247332230DEE32FA42524430CC
  91. D2077600823179E7E78FB97601C4143818F0981AF042034CA00004CA81AF0117
  92. 4143130169AC314234779208A250B4716914281AF0216413681AF08AC2819F0B
  93. 46808603F81A40A81AF10130D380FF0DDBD1C5808A040E5819F20D5DED4C5C5C
  94. 0C5C5C8C581AF11C0131152716F8FA4CB28F660C294BB0AF0AF1501152716F8F
  95. A4CB28F660C204E711A8A360618F0481AF1413117481AF1AC614517420342000
  96. 014517481AF19818FAF818FA41453435000C2134AF0AF18FB40C21FD54A28F3E
  97. FB28FB40C281AF1C1351741471741438B260610404C41C9141179179AF0AF12E
  98. B058F660C2A818F660C217F1741370613413517F17F179058FDFFB28F660C28F
  99. DFFB28F5BBB218F1848FB40C28598448F0E6B2071348FB40C2AF9AF7AF68FE19
  100. B2AF9AF7AF68FAC7B2BCC8F660C2D0B641410481AF1413016920347A000C2135
  101. 1421478B6606F030681AF141318F88AC0174143078BE6067D10617414304CAD8
  102. C5C5C0C5C5C0D5C6C6C1C6C6C1174147CAC906D6061741348F3EFB28FF6EB28F
  103. 130C2058FE19B28F16EB28F3EFB28F130C28FE19B28FBCEB2BCC8FAC7B28F660
  104. C207061348F130C21CF1CF1C98F3EFB28FE19B28F16EB28F130C28F0CEB28FE1
  105. 9B28FBCEB28FAC7B28F16EB2071350706818F2F818F24061348F130C28FB8EB2
  106. BCC8FAC7B213713513416F1648FB40C28F5BEB28F6DEB28FAC7B2071348FB40C
  107. 281AF142034E300004CA1308FDFFB28F16EB207061348F130C28FB8EB205BCC8
  108. FAC7B28F660C28F5BEB28F6DEB28FAC7B2071348FB40C281AF141311430704C2
  109. 06671E81AF1420344100004C2061343429000C2135058FDFFB28F16EB28F710C
  110. 28FE19B28FF6EB28F130C21CF1CF1C98F3EFB28FE19B2BCC8F6DEB28FAC7B28F
  111. BCEB28FAC7B2071348FB40C21CF1C48F3EFB28FBCEB28FE19B28F16EB28F130C
  112. 28FB8EB28F3EFB28FE19B28FBCEB28FAC7B28F6DEB28FAC7B281AF1C13416F16
  113. F1688FB40C214704E6E61456CCC04C414067EB81AF1413117414381AF02819F0
  114. 203191AF1A7504C405550B75A6E5DE25A3CB3481591D7FBF5AC08F16EB20481A
  115. F142034CA000C21341F975071471351C914781AF0B13517E1798FDFFB28FBCEB
  116. 2058F779B28F64E92151717F81AF1A04CE81AF0A8AE8C81AF138D27630B2130B
  117. 2130B2130157003064644530D9D20D29512BF8171040D9D20881308A7532FA30
  118. 6FD7388130CCD203300014713717414313504D6FCFA0EFEE44908D60B308DA1B
  119. 306FD735C2268DA1644230D9D20391402C2302CE3011920CA000CBD30D247332
  120. 230DEE32FA42524430CCD2082600823179E7E78FB97601C4143818F0981AF042
  121. 034CA00004CA81AF01174143130169AC314234779208A250B4716914281AF021
  122. 6413681AF08AC2819F0B46808603F81A40A81AF10130D380FF0DDBD1C5808A04
  123. 0E5819F20D5DED4C5C5C0C5C5C8C581AF11C0131152716F8FA4CB28F660C294B
  124. B0AF0AF1501152716F8FA4CB28F660C204E711A8A360618F0481AF1413117481
  125. AF1AC614517420342000014517481AF19818FAF818FA41453435000C2134AF0A
  126. F18FB40C21FD54A28F3EFB205BCC8FB40C281AF1C1351741471741438B260610
  127. 404C41C9141179179AF0AF12EB058F660C2A818F660C217F1741370613413517
  128. F17F179058FDFFB28F660C28FDFFB28F5BBB218F1848FB40C28598448F0E6B20
  129. 71348FB40C2AF9AF7AF68FE19B2AF9AF7AF68FAC7B2BCC8F660C2D0B64141048
  130. 1AF1413016920347A000C21351421478B6606F030681AF141318F88AC0174143
  131. 078BE6067D10617414304CAD8C5C5C0C5C5C0D5C6C6C1C6C6C1174147CAC906D
  132. 6061741348F3EFB28FF6EB28F130C2058FE19B28F16EB28F3EFB28F130C28FE1
  133. 9B28FBCEB2BCC8FAC7B28F660C207061348F130C21CF1CF1C98F3EFB28FE19B2
  134. 8F16EB28F130C28F0CEB28FE19B28FBCEB28FAC7B28F16EB2071350706818F2F
  135. 818F24061348F130C28FB8EB2BCC8FAC7B213713513416F1648FB40C28F5BEB2
  136. 8F6DEB28FAC7B2071348FB40C281AF142034E300004CA1308FDFFB28F16EB207
  137. 061348F130C28FB8EB205BCC8FAC7B28F660C28F5BEB28F6DEB28FAC7B207134
  138. 8FB40C281AF141311430704C206671E81AF1420344100004C2061343429000C2
  139. 135058FDFFB28F16EB28F710C28FE19B28FF6EB28F130C21CF1CF1C98F3EFB28
  140. FE19B2BCC8F6DEB28FAC7B28FBCEB28FAC7B2071348FB40C21CF1C48F3EFB28F
  141. BCEB28FE19B28F16EB28F130C28FB8EB28F3EFB28FE19B28FBCEB28FAC7B28F6
  142. DEB28FAC7B281AF1C13416F16F1688FB40C214704E6E61456CCC04C414067EB8
  143. 1AF1413117414781AF0A042034CA000C21341F975071471351C914781AF0B135
  144. 17E1798FDFFB2058F64E92151717F81AF1A04CE81AF0A8AE6D81AF138D27630B
  145. 2130B2130B21300EAF"
  146. END_ASC
  147.  
  148. BYTES: #FAE0h 2215
  149.  
  150. BEGIN_UU fft.uue
  151. begin 666 fft.dir
  152. M2%!(4#0X+4&6*O!_1@H````$4U!%0P2=+>!A(T@N,&!D1(7D`@1!0E-6A_N!
  153. MFQS)HG*V&M_0L=`?,P&B*QXY-K(2`V0`4!#D=,145-#9`BU9(?L8%T#0V0*(
  154. M,6`E8BP:AA@#J%>#K6&Y,=;N([2B(D0#S"U0#``H$T=^^)MG$#3!%'08^K`Q
  155. M%.9A&1-Q'C1Q%'1QQ(R*%D$31V$$A!^9`YWL&/K`^(C*$#47]S$&%G47]U#X
  156. MH+R";^\J^->V@F_D*7`Q%`47]ACZP4#L&/K`M8JA'X,O9P,K,;`2`RT!0!`D
  157. M-&5%T-D"+5DA^Q@70-#9`H@Q8"5B+!J&&`.H5X.M8;DQUNXCM*(B1`/,+0`.
  158. M`"@31W[XFV<0-,$4=!CZ@#$4YF$9$W$>-'$4=''$C(H601-'802$'YD#G>P8
  159. M^L#XB,H`=5*`_^8K=P0Q!H9O[2OXRK>"/Y\K^$:>`A=#47!ACZ$?#,2.H0]<
  160. MJMAO-A`U%_?X2KRBG_JG;_@>N0*Q$@,K,6`4``1)1D94!)TMT)(5LH]Q`02=
  161. M+8`8`ZA7(Z\#]GV#&`/,+3`#`$$7<W$4-#$%U/;\"O[N1`G8!CN`K;$#]GU3
  162. M+&+8&D8D`YTM,!D$PC(@[`,1*<`*`+P]T$(W(S+0[B.O)"5$`\PM<&<`*!.7
  163. M?G[XFV<03$&#@0^)H0\D,,0*`$"L&/H0<10T,1"6RA,D0W<I@"H%2Q>608*A
  164. M#Q)&,8:A#Z@L&/FP9`AH,(^A!(JA'Q`#/0C_T+T=7`BH0."%D2_0U=[$Q<7`
  165. MQ<7(A:$?P1`347)ACZ_$*_AFP)*T"_J@'P41)1?V^$J\@F\&+$!^$8HZ!A;X
  166. M0!CZ03$11QCZH6Q!%4<"0P(`$%1QA*$?B8&OCX&O%%1#4P#`$D/ZH!_X2\`2
  167. MWT4J^.._@K\$+!CZP3$51T$71T&#*P860$!,P1D4<1F7^J`?X@N%;P8LBH%O
  168. M!BQQ'T<Q!Q9#,17W<1^74/C]OX)O!BSX_;^"7[LK@1](^$O`@I5(A`]N*W`Q
  169. MA+\$+/JI?_J&[Y$K^JE_^H:O?"O+C&\&+`UK%!1`&/I!,1"6`D.G`,`24T$2
  170. M=+AF8`\#AJ$?%!/XB,H01T$#A^L&=AU@<10T0*R-7%P,7%P,76QL'&QL''$4
  171. M=*R<8&U@<11#^.._@O_F*_@QP`*%[Y$K^&&^@C_^*_@QP(+OD2OXR[ZRS/C*
  172. MMX)O!BQP8#&$'P,LP1_\P8D__BOX'KF"'^8K^#'`@@_L*_@>N8*_["OXRK>"
  173. M'^8K<#$%!X:!+X^!+P060_@QP(*_Z"O+C*]\*S$74S$4]F&$OP0L^+6^@F_M
  174. M*_C*MP(70_A+P(*A'R0PY`,`0*PQ@-__*_AAO@('%D/X,<""O^@K4,N,KWPK
  175. M^&;`@E_K*_C6OH*O?"MP,82_!"P8^D$Q$31P0"Q@=N$8^D$"0Q0``,0"%D-#
  176. MD@#`$E-0^/V_@A_F*_@7P(+OD2OX;[Z"'P,LP1_\P8D__BOX'KFRS/C6OH*O
  177. M?"OXR[Z"KWPK<#&$OP0LP1],^.._@K_L*_@>N8(?YBOX,<""O^@K^.._@N^1
  178. M*_C+OH*O?"OXUKZ"KWPK&/K!,13V81^&^$O`$G1`;FY!9<P,Q!0$=KX8^D$Q
  179. M$4=!@Z$/@I$/`A,9^J%70$Q05;!7:E[M4CJ\0QB5T??[I0SX8;X"A*$?)##$
  180. M"@`L,12?5W!!%U/!&708^K`Q%>=QB=__*_C+O@*%?Y<K^$:>$A47]QCZH4#L
  181. M&/J@J(Z,H1^#+6<#*S&P$@,K,1!U``-&1E0#G2W0DA6RCW$!!)TM@!@#J%<C
  182. MKP/V?8,8`\PM,`,`01=S<10T,074]OP*_NY$"=@&.X"ML0/V?5,L8M@:1B0#
  183. MG2TP&03",B#L`Q$IP`H`O#W00C<C,M#N(Z\D)40#S"V`8@`H$Y=^?OB;9Q!,
  184. M08.!#XFA#R0PQ`H`0*P8^A!Q%#0Q$);*$R1#=RF`*@5+%Y9!@J$/$D8QAJ$/
  185. MJ"P8^;!D"&@PCZ$$BJ$?$`,]"/_0O1U<"*A`X(61+]#5WL3%Q<#%Q<B%H1_!
  186. M$!-1<F&/K\0K^&;`DK0+^J`?!1$E%_;X2KR";P8L0'X1BCH&%OA`&/I!,1%'
  187. M&/JA;$$51P)#`@`05'&$H1^)@:^/@:\45$-3`,`20_J@'_A+P!+?12KXX[\"
  188. MM<SX2\""H1\<4W$4='$4-+AB8`$$Q!2<01&7<:D/^B&^4/AFP*(8^&;`$O=Q
  189. M%'-@,113<1_W<0F%W_\K^&;`@M__*_BUNQ+X@82_!"Q8B43XX+8"%T/X2\"B
  190. MG_JG;_@>N:*?^J=O^,JWLLSX9L#2L$9!`82A'Q0#82DP=`H`+#$5)$&':P;V
  191. M,&`8^D$Q@8^H#'$4-'"X;F#7`19'00/$VLC%Q<#%Q=#%QL;!QL811T''R@G6
  192. M!A9',80__BOX;[Z"'P,L4/@>N8(?YBOXX[^"'P,L^!ZY@K_L*\N,KWPK^&;`
  193. M`@<60_@QP!+\P1^<^.._@N^1*_AAOH(?`RSXP+Z"[Y$K^,N^@J]\*_AAO@(7
  194. M4W!@&/CR&/A"8#&$'P,L^(N^LLSXRK<2<S$50V$?1OA+P()?ZROXUKZ"KWPK
  195. M<#&$OP0L&/I!`D,^``#$&@/X_;^"'^8K<&`QA!\#+/B+O@*US/C*MX)O!BSX
  196. MM;Z";^TK^,JW`A=#^$O`@J$?%!-!`P?$`F87CJ$?)#!$`0!`+&`Q-"0)`"PQ
  197. M!87?_ROX8;Z"?P$L^!ZY@O_F*_@QP!+\P1^<^.._@N^1*\N,;^TK^,JW@K_L
  198. M*_C*MP(70_A+P!+\P80__BOXR[Z"[Y$K^&&^@A\#+/B+OH(__BOX'KF"O^PK
  199. M^,JW@F_M*_C*MX*A'QQ#81_V88B_!"Q!!^3F%E3&S$!,06#GBZ$?%!-Q%'08
  200. M^J!``D.L`,`20_%Y!1=T,16<08>A#QM3<1Z7^/V_`H5OY"E1<7&/H1\*Q(ZA
  201. 2#XKJUACZ,=AR-K`2`RLQL!(#
  202. `
  203. end
  204. END_UU
  205.  
  206.